// 递归搜索与回溯 - 决策树问题
// 当一个题目可以使用决策树画出来，那么也可以通过递归的方法解决
// 画决策树，要保证不重不漏
// 使用全局变量进行统计，避免递归函数头传参问题
// 设计递归函数头，是否需要记录本次决策的位置，层数，个数等信息
// 回溯时注意本层计算完成后，直接在本层回溯，返回上一个位置
// 经典题目：全排列，子集

// 例题 4：
// 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
//
//        示例 1：
//
//        输入：n = 3
//        输出：["((()))","(()())","(())()","()(())","()()()"]
//        示例 2：
//
//        输入：n = 1
//        输出：["()"]
//
//
//        提示：
//
//        1 <= n <= 8

import java.util.ArrayList;
import java.util.List;

// 解题思路：
// 暴力枚举左括号和右括号
// 当左括号的数量 >= 右括号的数量 并且 左括号的数量和右括号的数量相等，收集结果
// 左括号的数量超过 n ，剪枝
// 右括号数量大于左括号，剪枝
public class GenerateParenthesis {
    List<String> ret;
    StringBuilder path;
    int num = 0;
    int left = 0;
    int right = 0;
    public List<String> generateParenthesis(int n) {
        ret = new ArrayList<>();
        path = new StringBuilder();
        num = n;
        dfs();
        return ret;
    }
    public void dfs(){
        if(path.length() >= 2 * num){
            ret.add(new String(path));
            return;
        }
        if(left < num){
            path.append('(');
            left++;
            dfs();
            path.deleteCharAt(path.length() - 1);
            left--;
        }
        if(right < left){
            path.append(')');
            right++;
            dfs();
            path.deleteCharAt(path.length() - 1);
            right--;
        }
    }
}
